// https://leetcode-cn.com/problems/ugly-number-ii/

class Solution
{
public:
  int nthUglyNumber(int n)
  {
    vector<int> nums(n, 0);

    // 1 是一个丑数
    nums[0] = 1;

    // 2、3、5 三个质因子，不断变化的 nums 数组下标值
    int i2 = 0, i3 = 0, i5 = 0;

    // i: 1 ~ 1690
    while(i2 < n && i3 < n && i5 < n)
    {
      // 取出 2、3、5 作为【质因子】【最小】的一个元素值
      int ugly = Match.min(nums[i2] * 2, nums[i3] * 3, nums[i5] * 5);

      // 追加到 输出数组 末尾
      nums.push_back(ugly);

      // 确定 2、3、5 质因子 对应的 位置 +1
      if (ugly == nums[i2] * 2)
        i2 += 1;
      if (ugly == nums[i3] * 3)
        i3 += 1;
      if (ugly == nums[i5] * 5)
        i5 += 1;
    }
  }
};